package com.dmall.play.interview.chapter09;

import java.util.Arrays;

/**
 * 226 -> BZ VF BBF
 */
public class Leetcode91V3 {

    public int numDecodings(String s) {
        int[] memo = new int[s.length() + 1];
        Arrays.fill(memo, -1);
        return getAns(s, 0, memo);
    }

    private int getAns(String s, int start, int[] memo) {
        if (start == s.length()) {
            return 1;
        }
        if (s.charAt(start) == '0') {
            return 0;
        }
        //判断之前是否计算过
        int m = memo[start];
        if (m != -1) {
            return m;
        }
        int ans1 = getAns(s, start + 1, memo);
        int ans2 = 0;
        if (start < s.length() - 1) {
            int ten = (s.charAt(start) - '0') * 10;
            int one = s.charAt(start + 1) - '0';
            if (ten + one <= 26) {
                ans2 = getAns(s, start + 2, memo);
            }
        }
        //将结果保存
        memo[start] =  ans1 + ans2;
        return ans1 + ans2;
    }

    public static void main(String[] args) {
        Leetcode91V3 leetcode91 = new Leetcode91V3();
        System.out.println(leetcode91.numDecodings("226"));
    }
}
